package com.zhz.leetcode;

import com.zhz.leetcode.entity.TreeNode;

import java.util.*;

/**
 * 102. 二叉树的层序遍历
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 * <p>
 * 示例 1：
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 * <p>
 * 示例 2：
 * 输入：root = [1]
 * 输出：[[1]]
 * 示例 3：
 * <p>
 * 输入：root = []
 * 输出：[]
 * <p>
 * 提示：
 * <p>
 * 树中节点数目在范围 [0, 2000] 内
 * -1000 <= Node.val <= 1000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BinaryTreeLevelOrderTraversal102 {

    public static void main(String[] args) {
        BinaryTreeLevelOrderTraversal102 m = new BinaryTreeLevelOrderTraversal102();
        TreeNode root = new TreeNode(3,
                new TreeNode(9, null, null),
                new TreeNode(20,
                        new TreeNode(15), new TreeNode(7)));
        List<List<Integer>> list = m.levelOrder1(root);

        System.out.println(list);
    }

    /**
     * 自己的思路：
     * 将上一个层节点都加入到List<TreeNode>里面去
     * 接着下次递归的时候去获取上一层的所有node，，然后在获取下一层的所有node，加入到List<TreeNode>，知道最后一次的时候，node节点都是空的，
     * 然后再将节点信息的值取出来
     * 很罗嗦
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        List<List<TreeNode>> nodeList = new ArrayList<>();
        List<TreeNode> first = new ArrayList<>();
        first.add(root);
        nodeList.add(first);
        test(nodeList);
        for (int i = 0; i < nodeList.size(); i++) {
            List<TreeNode> tmp = nodeList.get(i);
            if (!tmp.isEmpty()) {
                List<Integer> c = new ArrayList<>();
                for (TreeNode node : tmp) {
                    c.add(node.val);
                }
                list.add(c);
            }
        }
        return list;
    }

    public void test(List<List<TreeNode>> list) {
        List<TreeNode> lastList = list.get(list.size() - 1);
        if (lastList == null || lastList.isEmpty()) {
            return;
        }
        List<TreeNode> currList = new ArrayList<>();
        for (int i = 0; i < lastList.size(); i++) {
            TreeNode node = lastList.get(i);
            if (node != null && node.left != null) {
                currList.add(node.left);
            }
            if (node != null && node.right != null) {
                currList.add(node.right);
            }
        }
        list.add(currList);
        test(list);
    }


    /**
     * 官方解法：使用广度优先搜索
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> subList = new ArrayList<>();
            while (size > 0) {
                TreeNode node = queue.poll();
                subList.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            list.add(subList);
        }

        return list;
    }


}
